<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
    <head>
        <title>RVM : IR</title>
	    <link rel="stylesheet" href="styles/site.css" type="text/css" />
        <META http-equiv="Content-Type" content="text/html; charset=UTF-8">	    
    </head>

    <body>
	    <table class="pagecontent" border="0" cellpadding="0" cellspacing="0" width="100%" bgcolor="#ffffff">
		    <tr>
			    <td valign="top" class="pagebody">
				    <div class="pageheader">
					    <span class="pagetitle">
                            RVM : IR
                                                    </span>
				    </div>
				    <div class="pagesubheading">
					    This page last changed on Jul 02, 2008 by <font color="#0050B2">dgrove</font>.
				    </div>

				    <p>The optimizing compiler intermediate representation (IR) is held in an object of type <tt>IR</tt> and includes a list of instructions. Every instruction is classified into one of the pre-defined instruction formats. Each instruction includes an operator and zero or more operands. Instructions are grouped into basic blocks; basic blocks are constrained to having control-flow instructions at their end. Basic blocks fall-through to other basic blocks or contain branch instructions that have a destination basic block label. The graph of basic blocks is held in the <tt>cfg</tt> (control-flow graph) field of IR.</p>

<p>This section documents basic information about the intermediate instruction. For a tutorial based introduction to the material it is highly recommended that you read "<a href="http://docs.codehaus.org/display/RVM/Presentations#Presentations-ir">Jikes RVM Optimizing Compiler Intermediate Code Representation</a>".</p>

<h2><a name="IR-IROperators"></a>IR Operators</h2>

<p>The IR operators are defined by the class <tt>Operators</tt>, which in turn is automatically generated from a template by a driver.  The input to the driver are two files, both called <tt>OperatorList.dat</tt>.  One input file resides in <tt>$RVM_ROOT/rvm/src-generated/opt-ir</tt> and defines machine-independent operators.  The other resides in <tt>$RVM_ROOT/rvm/src-generated/opt-ir/${arch</tt>} and defines machine-dependent operators, where <tt>${arch</tt>} is the specific instruction architecture of interest.</p>

<p>Each operator in <tt>OperatorList.dat</tt> is defined by a five-line record, consisting of:</p>
<ul>
	<li><tt>SYMBOL</tt>: a static symbol to identify the operator</li>
	<li><tt>INSTRUCTION_FORMAT</tt>: the instruction format class that accepts this operator.</li>
	<li><tt>TRAITS</tt>: a set of characteristics of the operator, composed with a bit-wise or (<em>&#124;</em>) operator.  See <tt>Operator.java</tt> for a list of valid traits.</li>
	<li><tt>IMPLDEFS</tt>: set of registers implicitly defined by this operator; usually applies only to machine-dependent operators</li>
	<li><tt>IMPLUSES</tt>: set of registers implicitly used by this operator; usually applies only to machine-dependent operators</li>
</ul>


<p>For example, the entry in <tt>OperatorList.dat</tt> that defines the integer addition operator is</p>
<div class="preformatted panel" style="border-width: 1px;"><div class="preformattedContent panelContent">
<pre>INT_ADD
Binary
none
&lt;blank line&gt;
&lt;blank line&gt;
</pre>
</div></div>
<p>The operator for a conditional branch based on values of two references is defined by</p>
<div class="preformatted panel" style="border-width: 1px;"><div class="preformattedContent panelContent">
<pre>REF_IFCOMP
IntIfCmp
branch | conditional
&lt;blank line&gt;
&lt;blank line&gt;
</pre>
</div></div>
<p>Additionally, the machine-specific <tt>OperatorList.dat</tt> file contains  another line of information for use by the assembler.  See the file for details.</p>

<h2><a name="IR-InstructionFormats"></a>Instruction Formats</h2>

<p>Every IR instruction fits one of the pre-defined <em>Instruction Formats</em>. The Java package <tt>com.ibm.jikesrvm.opt.ir</tt> defines roughly 75 architecture-independent instruction formats.  For each instruction format, the package includes a class that defines a set of static methods by which optimizing compiler code can access an instruction of that format.</p>

<p>For example, <tt>INT_MOVE</tt> instructions conform to the <tt>Move</tt> instruction format.  The following code fragment shows code that uses the <tt>Operators</tt> interface and the <tt>Move</tt> instruction format:</p>
<div class="code panel" style="border-style: solid;border-width: 1px;"><div class="codeHeader panelHeader" style="border-bottom-width: 1px;border-bottom-style: solid;"><b>X.java</b></div><div class="codeContent panelContent">
<pre class="code-java"><span class="code-keyword">import</span> com.ibm.jikesrvm.opt.ir.*;
class X {
  void foo(Instruction s) {
    <span class="code-keyword">if</span> (Move.conforms(s)) {     <span class="code-comment">// <span class="code-keyword">if</span> <span class="code-keyword">this</span> instruction fits the Move format
</span>      RegisterOperand r1 = Move.getResult(s);
      Operand r2 = Move.getVal(s);
      <span class="code-object">System</span>.out.println(<span class="code-quote">"Found a move instruction: "</span> + r1 + <span class="code-quote">" := "</span> + r2);
    } <span class="code-keyword">else</span> {
      <span class="code-object">System</span>.out.println(s + <span class="code-quote">" is not a MOVE"</span>);
    }
  }
}</pre>
</div></div>
<p>This example shows just a subset of the access functions defined for the Move format.  Other static access functions can set each operand  (in this case, <tt>Result</tt> and <tt>Val</tt>), query each operand for nullness, clear operands, create Move instructions, mutate other instructions into Move instructions, and check the index of a particular operand field in the instruction.  See the Javadoc<a href="http://docs.codehaus.org/display/RVM/Trademarks" title="Trademarks">™</a> reference for a complete description of the API.</p>

<p>Each fixed-length instruction format is defined in the text file <tt>$RVM_ROOT/rvm/src-generated/opt-ir/InstructionFormatList.dat</tt>. Each record in this file has four lines:</p>
<ul>
	<li><tt>NAME</tt>: the name of the instruction format</li>
	<li><tt>SIZES</tt>: the number of operands defined, defined and used, and used</li>
	<li><tt>SIG</tt>: a description of each operand, each description given by
	<ul>
		<li><tt>D/DU/U</tt>: Is this operand a def, use, or both?</li>
		<li><tt>NAME</tt>: the unique name to identify the operand</li>
		<li><tt>TYPE</tt>: the type of the operand (a subclass of <tt>Operand)</tt></li>
		<li><tt>[opt]</tt>: is this operand optional?</li>
	</ul>
	</li>
	<li><tt>VARSIG</tt>: a description of repeating operands, used for variable-length instructions.</li>
</ul>


<p>So for example, the record that defines the <tt>Move</tt> instruction format is</p>
<div class="preformatted panel" style="border-width: 1px;"><div class="preformattedContent panelContent">
<pre>Move
1 0 1
"D Result RegisterOperand" "U Val Operand"
&lt;blank line&gt;
</pre>
</div></div>
<p>This specifies that the <tt>Move</tt> format has two operands, one def and one use.  The def is called <tt>Result</tt> and must be of type <tt>RegisterOperand</tt>. The use is called <tt>Val</tt> and must be of type <tt>Operand</tt>.</p>

<p>A few instruction formats have variable number of operands.  The format for these records is given at the top of <tt>InstructionFormatList.dat</tt>. For example, the record for the variable-length <tt>Call</tt> instruction format is:</p>
<div class="preformatted panel" style="border-width: 1px;"><div class="preformattedContent panelContent">
<pre>Call
1 0 3 1 U 4
"D Result RegisterOperand" \
"U Address Operand" "U Method MethodOperand" "U Guard Operand opt"
"Param Operand"
</pre>
</div></div>
<p>This record defines the <tt>Call</tt> instruction format.  The second line indicates that this format always has at least 4 operands (1 def and 3 uses), plus a variable number of uses of one other type.  The trailing 4 on line 2 tells the template generator to generate special constructors for cases of having 1, 2, 3, or 4 of the extra operands. Finally, the record names the <tt>Call</tt> instruction operands and constrains the types.  The final line specifies the name and types of the variable-numbered operands.  In this case, a <tt>Call</tt> instruction has a variable number of (use) operands called <tt>Param</tt>. Client code can access the ith parameter operand of a <tt>Call</tt> instruction <tt>s</tt> by calling <tt>Call.getParam(s,i)</tt>.</p>

<p>A number of instruction formats share operands of  the same semantic meaning and name.  For convenience in accessing like instruction formats, the template generator supports four common operand access types:</p>
<ul>
	<li><tt>ResultCarrier</tt>: provides access to an operand of type <tt>RegisterOperand</tt> named <tt>Result</tt>.</li>
	<li><tt>GuardResultCarrier</tt>: provides access to an operand of type <tt>RegisterOperand</tt> named <tt>GuardResult</tt>.</li>
	<li><tt>LocationCarrier</tt>: provides access to an operand of type <tt>LocationOperand</tt> named <tt>Location</tt>.</li>
	<li><tt>GuardCarrier</tt>: provides access to an operand of type <tt>Operand</tt> named <tt>Guard</tt>.</li>
</ul>


<p>For example, for any instruction <tt>s</tt> that carries a <tt>Result</tt> operand (eg. <tt>Move</tt>, <tt>Binary</tt>, and <tt>Unary</tt> formats), client code can call <tt>ResultCarrier.conforms(s)</tt> and <tt>ResultCarrier.getResult(s)</tt> to access the <tt>Result</tt> operand.</p>

<p>Finally, a note on rationale.  Religious object-oriented philosophers will cringe at the InstructionFormats.  Instead, all this functionality could be implemented more cleanly with a hierarchy of instruction types exploiting (multiple) inheritance.  We rejected the class hierarchy approach due to efficiency concerns of frequent virtual/interface method dispatch and type checks.  Recent improvements in our interface invocation sequence and dynamic type checking algorithms may alleviate some of this concern.</p>

				    
                    			    </td>
		    </tr>
	    </table>
	    <table border="0" cellpadding="0" cellspacing="0" width="100%">
			<tr>
				<td height="12" background="http://docs.codehaus.org/images/border/border_bottom.gif"><img src="images/border/spacer.gif" width="1" height="1" border="0"/></td>
			</tr>
		    <tr>
			    <td align="center"><font color="grey">Document generated by Confluence on Jun 10, 2009 09:12</font></td>
		    </tr>
	    </table>
    </body>
</html>